'''
https://leetcode.cn/problems/minimum-path-sum/
'''
import heapq
from typing import List
import numpy as np

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        # 最后一列
        for i in range(m - 2, -1, -1):
            grid[i][-1] += grid[i + 1][-1]
        # 最后一列
        for j in range(n - 2, -1, -1):
            grid[-1][j] += grid[-1][j + 1]
        for i in range(m - 2, -1, -1):
            for j in range(n - 2, -1, -1):
                grid[i][j] = min(grid[i + 1][j], grid[i][j + 1]) + grid[i][j]
        return grid[0][0]

    # dijkstra
    def minPathSum2(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        distance = np.full((m, n), 10**9, dtype=int)
        distance[0][0] = grid[0][0]
        visited = np.full((m, n), False)

        heap = [(grid[0][0], 0, 0)]
        while heap:
            cost, x, y = heapq.heappop(heap)
            if visited[x][y]: continue
            visited[x][y] = True
            for nx, ny in [(x + 1, y), (x, y + 1)]:
                if 0 <= nx < m and 0 <= ny < n:
                    n_cost = min(distance[x][y] + grid[nx][ny], distance[nx][ny])
                    if n_cost < distance[nx][ny]:
                        distance[nx][ny] = n_cost
                        heapq.heappush(heap, (n_cost, nx, ny))
        return distance[-1][-1].item()

print(10**9 < 2**32-1)
print(10**9 , (2**31)-1)